#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <conio.h>
#include <windows.h>
#include "sqstack.h"

using namespace std;

typedef struct														//位置坐标结构体
{
	int x, y;
}position;

void solveMaze(vector<vector<int> > &);

const int dirX[4] = { 0, 1, 0, -1 };								//位移向量
const int dirY[4] = { 1, 0, -1, 0 };
int width, length;


int main()
{
	int num;
	fstream fp("maze.map", ios::in);

	fp >> width >> length;
	vector<vector<int> > map(length, vector<int>(width, 0));
	for(int i = 0; i < length; i++)									//从迷宫文件中读入迷宫地图
		for(int j = 0; j < width; j++)
		{
			fp >> num;
			map[i][j] = num;
		}
	fp.close();

	for(int i = 0; i < length; i++)									//在屏幕上输出迷宫
	{
		for(int j = 0; j < width; j++)
			cout << setw(4) << map[i][j];
		cout << endl;
	}

	cout << "Press anykey to begin.";
	getch();
	solveMaze(map);

	return 0;
}

//在指定坐标输出一个数
void printnum(position current, int num)
{
	COORD pos;
	pos.X = (short int)((current.y)*4+3);
	pos.Y = (short int)(current.x);
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
	printf("%-4d", num);
}

//在指定坐标输出一个字符串
void printchar(position current, const char *str)
{
	COORD pos;
	pos.X = (short int)((current.y)*4+3);
	pos.Y = (short int)(current.x);
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
	printf("%-4s", str);
}

//判断当前坐标是否可到达
bool posValid(vector<vector<int> > &map, position pos)
{
	int x, y;
	x = pos.x;
	y = pos.y;
	if(x < 0 || y < 0)
		return false;
	if(x >= length || y >= width)									//判断该点是否越界
		return false;
	if(!map[x][y])													//判断该点是否有墙
		return false;
	return true;
}

//走迷宫主程序
void solveMaze(vector<vector<int> > &map)
{
	int dir;
	bool valid;														//valid表示在当前坐标是否还有路可走
	vector<vector<bool> > visited(length, vector<bool>(width, false));
	SqStack<position> pos_stack;									//坐标栈， visited表示当前坐标点是否走过
	position start={0, 0}, end={length-1, width-1};					//起始点和终点

	for(int i = 0; i < length; i++)
		for(int j = 0; j < width; j++)
			visited[i][j] = !map[i][j];

	pos_stack.Push(start);											//将起始点压入栈
	
	while(!pos_stack.StackEmpty())
	{
		position current;

		valid = false;
		current = pos_stack.GetTop();								//当前坐标
		printnum(current, pos_stack.StackLength());

		if((current.x == end.x) && (current.y == end.y))			//判断是否到终点
			break;
		for(dir = 0; (dir <= 3) && (!valid); dir++)					//遍历每个方向
		{
			position next = {current.x+dirX[dir], current.y+dirY[dir]};

			if(posValid(map, next) && !visited[next.x][next.y])		//判断下一步是否没走过且可到达
			{
				visited[next.x][next.y] = true;
				valid = true;
				printchar(next, "\4\4\4");
				pos_stack.Push(next);								//若下一步可走，则将下一步的位置坐标压栈
			}
		}
		if(!valid)													//若遇到死路
		{
			position p = pos_stack.GetTop();
			visited[p.x][p.y] = true;
			printnum(p, 1);
			pos_stack.Pop();	
			printchar(pos_stack.GetTop(), "\4\4\4");
		}
		for(int i = 0; i <= 9000000; i++);							//延时函数
	}

	if(!pos_stack.StackEmpty())										//存在路径
	{
		int k = pos_stack.StackLength();
		position current;
		while(!pos_stack.StackEmpty())								//刷新地图
		{
			current = pos_stack.GetTop();
			map[current.x][current.y] = k;
			k--;
			pos_stack.Pop();
		}
	}
	else															//若栈为空，说明没有路可以到达终点
	{
		position final = {length, 0};
		printchar(final,"There isn't a valid route.");
	}
}